/* 哈夫曼树模板类声明与定义文件（header Plus Plus） */

// #pragma once  /* 编译器提供放头文件重复包含，部分旧版不支持 */
#ifndef _HANFUMAN_H_
#define _HANFUMAN_H_

#include <iostream>
#include <vector>
#include <queue>

using std::vector;

// 哈夫曼树节点
template <class T>
struct hfTree_node{
	T _weight = 0;    // 权值
	// 双亲与左右孩子
	hfTree_node<T>*_parent, *_left, *_right;

	hfTree_node(const T& weight = 0) : 
		_weight(weight), _parent (nullptr), _left(nullptr), _right(nullptr)
	{}
};


template<class T>
class HuffmanTree{
	typedef hfTree_node<T> hNode;

	// 按大于比较的函数对象 （创建小堆）
	struct Compare{
		bool operator() (const hNode*  l, const hNode*  r) const{
			return l->_weight > r->_weight;
		}
	};

public:
	// 构造
	HuffmanTree() : _root(nullptr){}
	
	// 将数据放入优先级队列
	std::priority_queue<hNode*, vector<hNode*>, Compare> pq;    
	HuffmanTree(const vector<T>& val, const T& invalid) {
		for (auto& i : val){
			if (invalid != i) pq.push(new hNode(i));   // 小堆
		}
		while (pq.size() > 1){
			hNode* left = pq.top();
			pq.pop();
			hNode* right = pq.top();
			pq.pop();
			// 构造二叉树
			hNode* parent = new hNode(left->_weight + right->_weight);    // 新节点权值是左右孩子权值之和
			parent->_left = left, parent->_right = right;
			left->_parent = parent, right->_parent = parent;

			pq.push(parent);
		}
		_root = pq.top();
	}

	hNode* getRoot(){
		return _root;
	}

	~HuffmanTree(){
		TreeDestroy(_root);
	}
private:
	hNode* _root;   //根节点

	void TreeDestroy(hNode*& root){
		if (root != nullptr){
			TreeDestroy(root->_left);
			TreeDestroy(root->_right);
			delete root;
			root = nullptr;
		}
	}
};
#endif



#if 0
void TestHuffmanTree()
{
	vector<int> v{1, 3, 5, 7};
	HuffmanTree<int> hf(v);
}

#endif